package code101_200.code1_10;

/**
 * 将有序数组转换为二叉搜索树
 * 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
 *
 * 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
 *
 * 输入：nums = [-10,-3,0,5,9]
 * 输出：[0,-3,9,-10,null,5]
 * 解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
 *
 *
 */
public class _108arrayToSearchTree {

    /**
     * 问题思考：
     * 二叉搜索树的定义：任何一个节点，左子树的值小于根节点，右子树的值大于根节点。构建整棵树的过程，也就相当于构建子树的过程，所以为动态规划
     * 平衡二叉树定义：任何一个节点，每个结点的左右两个子树的高度差绝对值不超过1
     * 本来准备使用栈的形式，但由于不会看了题解，最终决定使用递归方法
     *
     * 由于数组事先已经升序排列，所以根节点可一次性直接选择，且搜索树的中序遍历结果就为数组结果，故子问题又根据数组结果进行遍历。参考二分法
     * 执行用时：     * 0 ms     * , 在所有 Java 提交中击败了     * 100.00%     * 的用户
     * 内存消耗：     * 38.2 MB     * , 在所有 Java 提交中击败了     * 37.41%     * 的用户
     * @param nums
     * @return
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        int left = 0;
        int right = nums.length-1;
        return create(nums,left,right);
    }

    public TreeNode create(int[] nums,int left,int right){
        if(right<left){
            return null;
        }
        int mid = (left+right)/2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = create(nums,left,mid-1);
        root.right = create(nums,mid+1,right);
        return root;
    }

}
